package _17_graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author: mornd
 * @dateTime: 2023/6/24 - 21:31
 * 检查图是否存在环
 */
public class InspectionRing {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("网页基础");
        Vertex v2 = new Vertex("Java基础");
        Vertex v3 = new Vertex("Java Web");
        Vertex v4 = new Vertex("Spring框架");
        Vertex v5 = new Vertex("微服务框架");
        Vertex v6 = new Vertex("数据库");
        Vertex v7 = new Vertex("实战项目");

        v1.edges = List.of(new Edge(v3));
        v2.edges = List.of(new Edge(v3));
        v3.edges = List.of(new Edge(v4));
        v6.edges = List.of(new Edge(v4));
        v4.edges = List.of(new Edge(v5));
        v5.edges = List.of(new Edge(v7));
//        v7.edges = List.of();
        v7.edges = List.of(new Edge(v5));

        List<Vertex> graph = new ArrayList<>(List.of(v1, v2, v3, v4, v5, v6, v7));

        // 1. 统计每个顶点的入度
        for (Vertex v : graph) {
            for (Edge edge : v.edges) {
                edge.linked.inDegree++;
            }
        }
        // 2. 将入度为0的加入队列
        Queue<Vertex> queue = new LinkedList<>();
        for (Vertex vertex : graph) {
            if (vertex.inDegree == 0) {
                queue.offer(vertex);
            }
        }

        List<String> names = new ArrayList<>();
        // 3. 不断移除队列顶点，每移除一个顶点，其相邻顶点的入度-1，直至入度为0时，将相邻顶点入队
        while (!queue.isEmpty()) {
            Vertex poll = queue.poll();
            names.add(poll.name);
            for (Edge edge : poll.edges) {
                edge.linked.inDegree--;
                if (edge.linked.inDegree == 0) {
                    queue.offer(edge.linked);
                }
            }
        }

        boolean ring = graph.size() != names.size();
        System.out.println("是否存在环：" + ring);
    }
}
